package com.yaoli.ajob;

import java.util.*;

/**
 * Created by will on 2017/4/19.
 */
public class _494_TargetSum {
    public static void main(String[] args) {
        _494_TargetSum targetSum = new _494_TargetSum();

        int nums [] = {1,2,3,4,5};
//        int nums [] = {1, 1, 1, 1, 1};

        int s = targetSum.findTargetSumWays5(nums,3);

        System.out.println(s);
    }

    public int findTargetSumWays5(int[] nums, int s) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        if(sum < s || (s + sum) % 2 > 0){
            return 0;
        }else{
            return subsetSum(nums, (s + sum) / 2);
        }

    }

    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1];
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] = dp[i] + dp[i - n];
        return dp[s];
    }


    int result = 0;

    public int findTargetSumWays4(int[] nums, int S) {
        if (nums == null || nums.length == 0) return result;
        helper(nums, S, 0, 0);
        return result;
    }

    public void helper(int[] nums, int target, int pos, long eval){
        if (pos == nums.length) {
            if (target == eval) {
                result++;
            }
            return;
        }
        helper(nums, target, pos + 1, eval + nums[pos]);
        helper(nums, target, pos + 1, eval - nums[pos]);
    }



    public int findTargetSumWays3(int[] nums, int S) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        Map<String,Integer> map = new HashMap<>();
        int s = helper(nums, 0, 0, S, map);
        System.out.println("");
        return s;
    }
    private int helper(int[] nums, int index, int sum, int S, Map<String, Integer> map){
        String encodeString = index + "->" + sum;
        if (map.containsKey(encodeString)){
            return map.get(encodeString);
        }
        if (index == nums.length){
            if (sum == S){
                return 1;
            }else {
                return 0;
            }
        }
        int curNum = nums[index];
        int add = helper(nums, index + 1, sum - curNum, S, map);
        int minus = helper(nums, index + 1, sum + curNum, S, map);
        map.put(encodeString, add + minus);
        return add + minus;
    }

    public int findTargetSumWays2(int[] nums, int s) {
        int sum = 0;
        for(int i: nums) sum+=i;
        if(s>sum || s<-sum) return 0;
        int[] dp = new int[2*sum+1];
        dp[0+sum] = 1;
        for(int i = 0; i<nums.length; i++){
            int[] next = new int[2*sum+1];
            for(int k = 0; k<2*sum+1; k++){
                if(dp[k]!=0){
                    next[k + nums[i]] += dp[k];
                    next[k - nums[i]] += dp[k];
                }
            }
            dp = next;
        }
        return dp[sum+s];
    }


    public int findTargetSumWays(int[] nums, int S) {
        if(nums.length == 1 && (nums[0] == S || (-1)*nums[0] == S)){
            return 1;
        }

        int total = 0;

        HashSet<String> sets = new HashSet<String>();

        for(int i = 1 ;i < nums.length ;i++){
            HashMap<String,Integer> left = calc(nums,0,i);
            HashMap<String,Integer> right = calc(nums, i , nums.length);
            for(String m : left.keySet()){
                for(String n : right.keySet()){
                    if(left.get(m)+right.get(n) == S && !sets.contains(m+"+"+n)){
                        total++;
                        sets.add(m+"+"+n);
                    }
                }
            }
        }

        return total;
    }

    /**
     * @param nums 数组
     * @param begin 包括
     * @param end 不包括
     * @return
     */
//    public Set<String> calc(int [] nums,int begin ,int end){
//        Set<String> res = new HashSet<>();
//
//        if(end - begin == 1){
//            res.add(String.valueOf((-1)*nums[begin]));
//            res.add(String.valueOf(nums[begin]));
//        }else{
//            for (int i = begin ; i < end - 1; i++) {
//
//                Set<String> left = calc(nums,begin,i + 1);
//                Set<String> right = calc(nums,i + 1,end);
//
//                for(String m : left){
//                    for(String n : right){
//                        res.add(m+"+"+n);
//                    }
//                }
//
//            }
//        }
//        return res;
//    }

    public HashMap<String,Integer> calc(int [] nums, int begin , int end){
        HashMap<String,Integer> res = new HashMap<>();

        if(end - begin == 1){
            res.put(String.valueOf("-"+nums[begin]),(-1)*nums[begin]);
            res.put(String.valueOf("+"+nums[begin]),nums[begin]);
        }else{
            for (int i = begin ; i < end - 1; i++) {

                HashMap<String,Integer> left = calc(nums,begin,i + 1);
                HashMap<String,Integer> right = calc(nums,i + 1,end);

                for(String m : left.keySet()){
                    for(String n : right.keySet()){
                        res.put(m+"+"+n,left.get(m)+right.get(n));
                    }
                }

            }
        }
        return res;
    }
}
